// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/spdy/hpack/hpack_huffman_decoder.h"

#include <bitset>
#include <limits>

#include "base/logging.h"
#include "base/macros.h"
#include "base/rand_util.h"
#include "base/strings/string_piece.h"
#include "net/spdy/hpack/hpack_constants.h"
#include "net/spdy/hpack/hpack_huffman_table.h"
#include "net/spdy/hpack/hpack_input_stream.h"
#include "net/spdy/hpack/hpack_output_stream.h"
#include "net/spdy/spdy_test_utils.h"
#include "testing/gtest/include/gtest/gtest.h"

using base::StringPiece;

namespace net {
namespace test {

    namespace {

        uint32_t RandUint32()
        {
            return static_cast<uint32_t>(base::RandUint64() & 0xffffffff);
        }

    } // anonymous namespace

    // Bits(HuffmanWord) constructs a bitset<32>, which produces nicely formatted
    // binary numbers when LOG'd.
    typedef std::bitset<32> Bits;

    typedef HpackHuffmanDecoder::HuffmanWord HuffmanWord;
    typedef HpackHuffmanDecoder::HuffmanCodeLength HuffmanCodeLength;

    class HpackHuffmanDecoderPeer {
    public:
        static HuffmanCodeLength CodeLengthOfPrefix(HuffmanWord value)
        {
            return HpackHuffmanDecoder::CodeLengthOfPrefix(value);
        }

        static HuffmanWord DecodeToCanonical(HuffmanCodeLength code_length,
            HuffmanWord bits)
        {
            return HpackHuffmanDecoder::DecodeToCanonical(code_length, bits);
        }

        static char CanonicalToSource(HuffmanWord canonical)
        {
            return HpackHuffmanDecoder::CanonicalToSource(canonical);
        }
    };

    // Tests of the ability to decode the HPACK Huffman Code, defined in:
    //     https://httpwg.github.io/specs/rfc7541.html#huffman.code
    class HpackHuffmanDecoderTest : public ::testing::Test {
    protected:
        HpackHuffmanDecoderTest()
            : table_(ObtainHpackHuffmanTable())
        {
        }

        // Since kHpackHuffmanCode doesn't include the canonical symbol value,
        // this helper helps us to decode directly to the source symbol, allowing
        // for EOS.
        uint16_t DecodeToSource(HuffmanCodeLength code_length, HuffmanWord bits)
        {
            HuffmanWord canonical = HpackHuffmanDecoderPeer::DecodeToCanonical(code_length, bits);
            EXPECT_LE(canonical, 256u);
            if (canonical == 256u) {
                return canonical;
            }
            return static_cast<unsigned char>(
                HpackHuffmanDecoderPeer::CanonicalToSource(canonical));
        }

        void EncodeString(StringPiece input, std::string* encoded)
        {
            HpackOutputStream output_stream;
            table_.EncodeString(input, &output_stream);
            encoded->clear();
            output_stream.TakeString(encoded);
            // Verify EncodedSize() agrees with EncodeString().
            EXPECT_EQ(encoded->size(), table_.EncodedSize(input));
        }

        std::string EncodeString(StringPiece input)
        {
            std::string result;
            EncodeString(input, &result);
            return result;
        }

        const HpackHuffmanTable& table_;
    };

    TEST_F(HpackHuffmanDecoderTest, CodeLengthOfPrefix)
    {
        for (const HpackHuffmanSymbol& entry : HpackHuffmanCode()) {
            // First confirm our assumption that the low order bits of entry.code
            // (those not part of the high order entry.length bits) are zero.
            uint32_t non_code_bits = 0xffffffff >> entry.length;
            EXPECT_EQ(0u, entry.code & non_code_bits);

            // entry.code has a code length of entry.length.
            EXPECT_EQ(entry.length,
                HpackHuffmanDecoderPeer::CodeLengthOfPrefix(entry.code))
                << "Full code: " << Bits(entry.code) << "\n"
                << "       ID: " << entry.id;

            // Let's try again with all the low order bits set to 1.
            uint32_t bits = entry.code | (0xffffffff >> entry.length);
            EXPECT_EQ(entry.length, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits))
                << "Full code: " << Bits(entry.code) << "\n"
                << "     bits: " << Bits(bits) << "\n"
                << "       ID: " << entry.id;

            // Let's try again with random low order bits.
            uint32_t rand = RandUint32() & (0xffffffff >> entry.length);
            bits = entry.code | rand;
            EXPECT_EQ(entry.length, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits))
                << "Full code: " << Bits(entry.code) << "\n"
                << "     rand: " << Bits(rand) << "\n"
                << "     bits: " << Bits(bits) << "\n"
                << "       ID: " << entry.id;

            // If fewer bits are available and low order bits are zero after left
            // shifting (should be true), CodeLengthOfPrefix should never return
            // a value that is <= the number of available bits.
            for (uint8_t available = entry.length - 1; available > 0; --available) {
                uint32_t mask = 0xffffffff;
                uint32_t avail_mask = mask << (32 - available);
                bits = entry.code & avail_mask;
                EXPECT_LT(available, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits))
                    << "Full code: " << Bits(entry.code) << "\n"
                    << "availMask: " << Bits(avail_mask) << "\n"
                    << "     bits: " << Bits(bits) << "\n"
                    << "       ID: " << entry.id;
            }
        }
    }

    TEST_F(HpackHuffmanDecoderTest, DecodeToSource)
    {
        for (const HpackHuffmanSymbol& entry : HpackHuffmanCode()) {
            // Check that entry.code, which has all the low order bits set to 0,
            // decodes to entry.id.
            EXPECT_EQ(entry.id, DecodeToSource(entry.length, entry.code))
                << "   Length: " << entry.length << "\n"
                << "Full code: " << Bits(entry.code);

            // Let's try again with all the low order bits set to 1.
            uint32_t bits = entry.code | (0xffffffff >> entry.length);
            EXPECT_EQ(entry.id, DecodeToSource(entry.length, bits))
                << "   Length: " << entry.length << "\n"
                << "Full code: " << Bits(entry.code) << "\n"
                << "     bits: " << Bits(bits);

            // Let's try again with random low order bits.
            uint32_t rand = RandUint32() & (0xffffffff >> entry.length);
            bits = entry.code | rand;
            EXPECT_EQ(entry.id, DecodeToSource(entry.length, bits))
                << "   Length: " << entry.length << "\n"
                << "Full code: " << Bits(entry.code) << "\n"
                << "     rand: " << Bits(rand) << "\n"
                << "     bits: " << Bits(bits);
        }
    }

    TEST_F(HpackHuffmanDecoderTest, SpecRequestExamples)
    {
        std::string buffer;
        std::string test_table[] = {
            a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"),
            "www.example.com",
            a2b_hex("a8eb10649cbf"),
            "no-cache",
            a2b_hex("25a849e95ba97d7f"),
            "custom-key",
            a2b_hex("25a849e95bb8e8b4bf"),
            "custom-value",
        };
        // Round-trip each test example.
        for (size_t i = 0; i != arraysize(test_table); i += 2) {
            const std::string& encodedFixture(test_table[i]);
            const std::string& decodedFixture(test_table[i + 1]);
            HpackInputStream input_stream(encodedFixture);
            EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buffer));
            EXPECT_EQ(decodedFixture, buffer);
            buffer = EncodeString(decodedFixture);
            EXPECT_EQ(encodedFixture, buffer);
        }
    }

    TEST_F(HpackHuffmanDecoderTest, SpecResponseExamples)
    {
        std::string buffer;
        // clang-format off
  std::string test_table[] = {
    a2b_hex("6402"),
    "302",
    a2b_hex("aec3771a4b"),
    "private",
    a2b_hex("d07abe941054d444a8200595040b8166"
            "e082a62d1bff"),
    "Mon, 21 Oct 2013 20:13:21 GMT",
    a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43"
            "d3"),
    "https://www.example.com",
    a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960"
            "d5af27087f3672c1ab270fb5291f9587"
            "316065c003ed4ee5b1063d5007"),
    "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
  };
        // clang-format on
        // Round-trip each test example.
        for (size_t i = 0; i != arraysize(test_table); i += 2) {
            const std::string& encodedFixture(test_table[i]);
            const std::string& decodedFixture(test_table[i + 1]);
            HpackInputStream input_stream(encodedFixture);
            EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buffer));
            EXPECT_EQ(decodedFixture, buffer);
            buffer = EncodeString(decodedFixture);
            EXPECT_EQ(encodedFixture, buffer);
        }
    }

    TEST_F(HpackHuffmanDecoderTest, RoundTripIndividualSymbols)
    {
        for (size_t i = 0; i != 256; i++) {
            char c = static_cast<char>(i);
            char storage[3] = { c, c, c };
            StringPiece input(storage, arraysize(storage));
            std::string buffer_in = EncodeString(input);
            std::string buffer_out;
            HpackInputStream input_stream(buffer_in);
            EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buffer_out));
            EXPECT_EQ(input, buffer_out);
        }
    }

    // Creates 256 input strings, each with a unique byte value i used to sandwich
    // all the other higher byte values.
    TEST_F(HpackHuffmanDecoderTest, RoundTripSymbolSequences)
    {
        std::string input;
        std::string encoded;
        std::string decoded;
        for (size_t i = 0; i != 256; i++) {
            input.clear();
            auto ic = static_cast<char>(i);
            input.push_back(ic);
            for (size_t j = i; j != 256; j++) {
                input.push_back(static_cast<char>(j));
                input.push_back(ic);
            }
            EncodeString(input, &encoded);
            HpackInputStream input_stream(encoded);
            EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &decoded));
            EXPECT_EQ(input, decoded);
        }
    }

} // namespace test
} // namespace net
